package com.kevin.Code.DivideandConquer;

/**
 * @author Vinlee Xiao
 * @Classname Leetcode50_powxn
 * @Description Leetcode 50. Pow(x, n) 中等难度  快速幂 细节问题处理不当
 * @Date 2021/12/1 14:09
 * @Version 1.0
 */
public class Leetcode50_powxn {

    /**
     * 这题要对数据的存储有清晰的认识 暴力法 超过时间限制
     * 从浅薄的知识中理解 写答案
     *
     * @param x
     * @param n
     * @return
     */
    public double myPow(double x, int n) {

        if (n == 1 || x == 0 || x == 1) {

            return x;
        }

        double result = 1;
        long iteration = n;

        if (n < 0) {
            x = 1 / x;
            iteration = -iteration;
        }

        for (int i = 0; i < iteration; i++) {

            result = result * x;
        }

        return result;
    }

    /**
     * 分治法
     *
     * @param x
     * @param n
     * @return
     */
    public double myPow1(double x, int n) {

        if (n == 1 || x == 0 || x == 1) {

            return x;
        }

        if (n < 0) {
            return 1 / myPower(x, -n);
        } else {
            return myPower(x, n);
        }
    }

    /**
     * 分治法
     *
     * @param x
     * @param n
     * @return
     */
    private double myPower(double x, int n) {
        //递归结束条件
        if (n == 0) {
            return 1.0;
        }

        double temp = myPower(x, n / 2);

        //位运算符判断奇偶
        if ((n & 1) == 0) {
            return temp * temp;
        } else {
            return temp * temp * x;
        }

    }


    /**
     * 小细节值得注意
     * 当n取正时会使数据产生越界 应而应定义位long型
     *
     * @param x
     * @param n
     * @return
     */
    public double myPow2(double x, int n) {

        if (n == 1 || x == 0 || x == 1) {
            return x;
        }
        long countNum = n;
        if (n < 0) {
            return 1 / calPow(x, -countNum);
        } else {
            return calPow(x, countNum);
        }

    }

    /**
     * 快速幂
     *
     * @param x
     * @param n
     * @return
     */
    private double calPow(double x, long n) {

        double result = 1.0;

        double cal_num = x;

        while (n > 0) {

            //奇数
            if (n % 2 == 1) {

                result = result * cal_num;
            }

            cal_num = cal_num * cal_num;
            n = n / 2;
        }

        return result;
    }

}
